package danran.bfs;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Classname LadderLength
 * @Description TODO
 * @Date 2021/8/26 20:34
 * @Created by ASUS
 */
public class LadderLength {

    public static void main(String[] args) {
        List<String> wordlist = new ArrayList<>(Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
        int i = new LadderLength().ladderLength("hit", "cog", wordlist);
        System.out.println(i);
        System.out.println(new LadderLength().findLadders("hit", "cog", wordlist));
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) return new ArrayList<>();
        Set<String> set = new HashSet<>(wordList);
        Queue<String> q = new ArrayDeque<>();
        Queue<List<String>> pre = new ArrayDeque<>();
        q.offer(beginWord);
        List<List<String>> ans = new ArrayList<>();
        List<String> begin = new ArrayList<>();
        Map<List<String>, Integer> map = new HashMap<>();
        pre.offer(begin);
        map.put(begin, 1);
        boolean find = false;
        int length = Integer.MAX_VALUE;
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            level++;
            for (int i = 0; i < size; i++) {
                List<String> curPre = pre.poll();
                Integer pres = map.get(curPre);
                for (int j = 0; j < pres; j++, i++) {
                    String cur = q.poll();
                    assert curPre != null;
                    List<String> temp = new ArrayList<>(curPre);
                    temp.add(cur);
                    assert cur != null;
                    if (cur.equals(endWord) && level <= length) {
                        ans.add(temp);
                        find = true;
                        length = level;
                        continue;
                    }
                    if (find) continue;
                    int cnt = 0;
                    for (int k = 0; k < cur.length(); k++) {
                        String[] words = this.getWords(cur, k);
                        for (String word : words) {
                            if (set.contains(word)) {
                                q.offer(word);
                                cnt++;
                            }
                        }
                    }
                    pre.offer(temp);
                    map.put(temp, cnt);
                }
                i--;
            }
        }
        return ans;
    }


    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) return 0;
        Set<String> dict = new HashSet<>(wordList);
        Queue<String> q = new ArrayDeque<>();
        q.offer(beginWord);
        StringBuilder curBuilder;
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            step++;
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                assert cur != null;
                if (cur.equals(endWord)) return step;
                curBuilder = new StringBuilder(cur);
                for (int k = 0; k < curBuilder.length(); k++) {
                    String[] words = this.getWords(curBuilder.toString(), k);
                    for (String word : words) {
                        if (word.equals(endWord)) return step + 1;
                        if (dict.contains(word)) {
                            q.offer(word);
                            dict.remove(word);
                        }
                    }
                }
            }
        }
        return 0;
    }

    public String[] getWords(String s, int index) {
        String[] ans = new String[25];
        StringBuilder src = new StringBuilder(s);
        int j = 0;
        char t = src.charAt(index);
        for (int i = 0; i < 26; i++) {
            char ch = (char) ('a' + i);
            if (ch != t) {
                src.replace(index, index+1, String.valueOf(ch));
                ans[j++] = src.toString();
            }
        }
        return ans;
    }
}
